#include <vector>

using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if ((m + n) % 2 == 1) {
            int k = (m + n)/2 + 1;  // kth element
            return getKthElement(nums1, nums2, k);
        } else {
            int k = (m + n)/2;
            return (getKthElement(nums1, nums2, k) + getKthElement(nums1, nums2, k+1))/2.0;
        }
    }

    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();
        int pos1 = 0, pos2 = 0;

        while (true) {
            // Edge cases
            if (pos1 == m) return nums2[pos2 + k - 1];  // k - 1 是索引值
            if (pos2 == n) return nums1[pos1 + k - 1];  // k - 1 是索引值
            if (k == 1) return min(nums1[pos1], nums2[pos2]);

            // Normal cases
            int curr1 = min(pos1+k/2-1, m-1);  // k/2-1 是增加的索引值
            int curr2 = min(pos2+k/2-1, n-1);  // k/2-1 是增加的索引值
            int pivot1 = nums1[curr1];
            int pivot2 = nums2[curr2];
            if (pivot1 <= pivot2) {
                k -= curr1 - pos1 + 1;  // + 1 是为了将 k 的索引值 转为 k 的序号值
                pos1 = curr1 + 1;
            } else {
                k -= curr2 - pos2 + 1;  // + 1 是为了将 k 的索引值 转为 k 的序号值
                pos2 = curr2 + 1;
            }
        }
    }
};
